//package personal.abandoned;
//
//import personal.scanner.ScannerFiniteAutomata;
//import personal.util.Utilities;
//import personal.util.Graph;
//import personal.util.IdAllocter;
//
//import java.util.*;
//
///**
// * 将 NFA 转换成 DFA 的转换器，默认：1 号节点为开始节点；空集的 id 为 0。注意：转移到空集说明没有转移边，是非法转移
// *
// * @author 陈渤林
// */
//public class NFAToDFAConverter {
//    /**
//     * 用于自动分配子集 id
//     */
//    public IdAllocter<Set<Integer>> alloc;
//
//
//    /**
//     * 将 nfa 转换成 dfa，并初始化子集 id 构造表、可接受集合表
//     *
//     * @param nfa         传入的 nfa
//     * @param transitions 字母表
//     * @param startId     自动机开始编号
//     * @return 转化出的 dfa
//     */
//    public ScannerFiniteAutomata convert(final ScannerFiniteAutomata nfa, Set<Integer> transitions, int startId) {
//        this.alloc = new IdAllocter<>(startId); // 初始化
//        ScannerFiniteAutomata dfa = new ScannerFiniteAutomata();
//        Queue<Set<Integer>> qe = new LinkedList<Set<Integer>>(); // 待更新队列
//        // 放入初始子集
////        this.alloc.getId(this.closureOfEmpty(new HashSet<Integer>(Arrays.asList(startId)), nfa));
//        this.alloc.getId(Utilities.closureByTransit(nfa, new HashSet<Integer>(Arrays.asList(startId)), ScannerFiniteAutomata.emptyTransit));
//        this.alloc.pollAllTo(qe);
//        // 循环
//        while (!qe.isEmpty()) { // 当还有需要更新的子集
//            // 设当前需要更新的子集为 su
//            Set<Integer> su = qe.poll(); // 从队首取出 su
//            for (Integer T : transitions) {// 对于该子集的每一个转移 T
//                // 设能转移到的子集为 sv
//                if (T == ScannerFiniteAutomata.emptyTransit) // 跳过空集
//                    continue;
//                Set<Integer> sv = new HashSet<Integer>(); // sv 初始化为空集
//                for (Integer u : su) { // 对于 su 中的每一个元素 u
//                    for (Graph.Node tmp : nfa.getOutEdgeAdjacencyList().get(u)) { // 将 u 的 T 转移放入 sv 中
//                        int w = tmp.w, v = tmp.v;
//                        if (w == T) sv.add(v);
//                    }
//                }
////                sv = closureOfEmpty(sv, nfa); // 加入 sv 中各元素的空串转移
//                sv = Utilities.closureByTransit(nfa, sv, ScannerFiniteAutomata.emptyTransit); // 加入 sv 中各元素的空串转移
//                if (sv.isEmpty()) continue; // 跳过空集！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
//                dfa.addEdge(this.alloc.getId(su), this.alloc.getId(sv), T); // su 的 T 转移为 sv
//                // 将新节点放入队列中
//                this.alloc.pollAllTo(qe);
//            }
//        }
//        // 记录可接受信息
//        for (Map.Entry<Integer, Set<Integer>> kv : this.alloc.getIdToObject().entrySet()) {
//            // 取交集：当前集合与 nfa 接受集合
//            Set<Integer> acceptableNode = Utilities.getIntersectionSet(kv.getValue(), nfa.getAcceptNodes().keySet());
//            if (!acceptableNode.isEmpty()) { // 交集非空 == 包含可接受节点
//                // 检查是否存在多个接受值
//                Set<Integer> acceptValues = new HashSet<Integer>();
//                for (int u : acceptableNode) acceptValues.add(nfa.getAcceptNodes().get(u));
//                if (acceptValues.size() > 1) System.out.println(String.format("检测到节点 %d 存在多个接受值"));
//                // 放入最小值
//                dfa.registerAcceptableNode(kv.getKey(), Collections.min(acceptValues));
//            }
//        }
//        dfa.setStartId(startId);
//        return dfa;
//    }
//
//
//}
